//Cracding coding interview 5.5, 5.6,5.7 
//7:58PM--8:01PM--8:06PM

#include<iostream>
#include<bitset>
#include<vector>
using namespace std;

int NumBits(int a, int b)
{
	int c=a^b;
	int count=0;
	while(c) {
		count++;
		c&=c-1;
	}
	return count;
}

int SwapBits(int a) {
	
	//bitset<32> bs("10101010101010101010101010101010");
	int mask0=0xaaaaaaaa;
	int mask1=0x55555555;

	int c0=a&mask0;
	int c1=a&mask1;
	return (c0>>1)|(c1<<1);
}

//8:13PM--8:22PM
int GetPartSum(vector<bitset<32>>& input, int pos, int step, int offset) {
	int retVal=input[offset][pos];
	for(int i=step; i<input.size(); i+=step) {
		retVal |= input[i][pos];
	}
	return retVal;
}

int FindInt(vector<bitset<32>>& input, bitset<32>& output, int pos=0) {
	if(input.size()==0) {
		return -1;
	}

	int n=input.size();
	vector<bitset<32>> zeros;
	zeros.reserve(n);
	vector<bitset<32>> ones;
	ones.reserve(n);
	for(int i=0; i<n; i++) {
		bitset<32> bs=input[i];
		if(bs[pos]) {
			ones.push_back(bs);
		} else {
			zeros.push_back(bs);
		}
	}

	if(n%2) {
		if(ones.size()<zeros.size()) {
			FindInt(ones, output, pos+1);
			output.set(pos);
		} else {
			FindInt(zeros, output, pos+1);
			output.reset(pos);
		}
	} else {
		if(ones.size()<zeros.size()) {
			FindInt(ones, output, pos+1);
			output.set(pos);
		} else {
			FindInt(zeros, output, pos+1);
			output.reset(pos);
		}
	}

	return output.to_ulong();
}


int main(int argc, char *argv[]) {
	int a=31, b=14;
	int c=NumBits(a, b);
	int d=SwapBits(a);

	int n=13;
	int j=3;
	vector<bitset<32>> input(n+1);
	for (int i=0; i<=n; i++) {
		bitset<32> u(i);
		input[i]=u;
	}
	input.erase(input.begin()+j);
	int e=FindInt(input, bitset<32>());


	return 0;
}